package Top_Interview_Questions_Review.Greedy;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/1 11:23
 * <p>
 * 功能描述:
 */
public class _0053 {

    public static void main(String[] args) {
        _0053 test = new _0053();

        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int max = test.maxSubArray2(nums);
        System.out.println(max);

    }

    /*----------------------------------------动态规划----------------------------------------*/

    /**
     *
     * https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
     */
    public int maxSubArray2(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }


    /*--------------------------------------------------------------------------------------*/



    /*----------------------------------------贪心算法----------------------------------------*/

    /**
     * 这个也是官方题解
     * https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode/
     *
     * 什么是贪心算法
     * https://baijiahao.baidu.com/s?id=1642122740570394361&wfr=spider&for=pc
     */
    public int maxSubArray1(int[] nums) {
        int n = nums.length;
        int currSum = nums[0];//当前元素位置的最大和

        int maxSum = nums[0];//迄今为止的最大和

        for (int i = 1; i < n; ++i) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }

    /*--------------------------------------------------------------------------------------*/



    /*----------------------------------------分治法-----------------------------------------*/

    /**
     * https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode/
     * <p>
     * 评论: 是一个浙大在mocc上的课程，b站有up上传了视频。这个链接里面的第一章的例题就是这个题。
     * 方法三就是分治算法，陈越老师分析的很详细
     * https://www.bilibili.com/video/av18586085
     * <p>
     * 注: 分治法有点难理解,代码也很长，以后再看
     */
    public int maxSubArray(int[] nums) {

        return 0;
    }

    /*--------------------------------------------------------------------------------------*/
}
